package com.zdp.algorithm.stackandqueue;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * 单调栈
 * 给定一个不含有重复值的数组arr，
 * 找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置。
 * 返回所有位置相应的信息。
 * @author Zhengdp
 * @date 2023年01月08日 15:05
 */
@Slf4j
public class MonotonicStack {
    private static final int[] arr = new int[]{
            3,4,1,5,6,2,7
    };

    private static int[][] result = new int[][]{
            {-1,2},{0,2},{-1,-1},{2,5},
            {3,5},{2,-1},{5,-1}
    };
    public static void main(String[] args) {
        MonotonicStackImpl impl = new MonotonicStackImpl();
        int[][] nearLess = impl.getNearLess(arr);
        boolean flag = true;
        for(int i = 0; i < nearLess.length;i++){
            int[] temp = nearLess[i];
            int[] tt = result[i];
            flag = temp[0] == tt[0] && temp[1] == tt[1];
        }
        log.info("最终结果 : {}",flag);
    }
}

/**
 * 单调栈实现该功能
 * 单调栈 ：栈顶到栈底 单调递减 ==> 栈顶元素是栈中的最大元素
 * 栈存储的数据为 元素的下标
 * 这个单调栈可以满足一个条件： 栈弹出的元素后，该元素的左边最近小于元素为新的栈顶元素
 * 所以，当满足第二个条件：栈顶元素的右边最近小于元素出现，就可以生成栈顶元素的二元组了。
 * 当数组遍历完成，手动弹出栈顶元素（这些栈顶元素右边无小于他们的元素值）
 * 【如何处理有重复值】 ==> Stack中存放数组Stack<List<Integer>> ==> 相同元素就放到一起
 */
class MonotonicStackImpl {

    public int[][] getNearLess(int[] arr) {
        Stack<Integer> monotonicStack = new Stack<>();
        int[][] result = new int[arr.length][2];
        for(int i = 0; i< arr.length ; i ++){
            int curNum = arr[i];
            while(!monotonicStack.isEmpty() && monotonicStack.peek() > curNum) {
                int popNum = monotonicStack.pop();
                int left = monotonicStack.isEmpty()? -1 : monotonicStack.peek();
                result[popNum] = new int[]{left,curNum};
            }
            monotonicStack.push(i);
        }
        while(!monotonicStack.isEmpty()) {
            int popNum = monotonicStack.pop();
            int left = monotonicStack.isEmpty()? -1 : monotonicStack.peek();
            result[popNum] = new int[]{left,-1};
        }
        return result;
    }

}
